#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;


class Queue {
public:
    virtual void enqueue(int value)=0;  
    virtual int dequeue()=0;             
    virtual bool isEmpty() const=0;  
    virtual void printQueue() const=0;  
    virtual ~Queue() {}
};


class MaxQueue : public Queue {
private:
    deque<int> data;

public:
    void enqueue(int value) {
        data.push_back(value);
    }

    int dequeue(){
        if (data.empty()) {
            perror("Queue is empty");
        }
  
        auto maxIter = max_element(data.begin(), data.end());
        int maxValue = *maxIter;
        data.erase(maxIter);
        return maxValue;
    }

    
    bool isEmpty() const {
        return data.empty();
    }

    
    void printQueue() const  {
        cout << "MaxQueue: ";
        for (int val : data) {
            cout << val << " ";
        }
        cout << endl;
    }
};


class MinQueue : public Queue {
private:
    deque<int> data;

public:
    void enqueue(int value) {
        data.push_back(value);
    }

    int dequeue() {
        if (data.empty()) {
            perror("Queue is empty");
        }
     
        auto minIter = min_element(data.begin(), data.end());
        int minValue = *minIter;
        data.erase(minIter);
        return minValue;
    }

    
    bool isEmpty() const {
        return data.empty();
    }

  
    void printQueue() const {
        cout << "MinQueue: ";
        for (int val : data) {
            cout << val << " ";
        }
        cout << endl;
    }
};



int main() {
    MaxQueue maxQueue;
    MinQueue minQueue;

    maxQueue.enqueue(15);
    maxQueue.enqueue(25);
    maxQueue.enqueue(5);
    maxQueue.enqueue(17);

    maxQueue.printQueue();

    cout << "Dequeue: " << maxQueue.dequeue() << endl;
    maxQueue.printQueue();


    minQueue.enqueue(12);
    minQueue.enqueue(2);
    minQueue.enqueue(3);
    minQueue.enqueue(16);

    minQueue.printQueue();

    cout << "Dequeue: " << minQueue.dequeue() << endl;
    minQueue.printQueue();

    return 0;
}